/**
 * LeetCode78：子集
 * 给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集
 */

/**
 *
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums){
    const res = [];
    /**
     *
     * @param path 当前拼接的子集
     * @param l 子集的长度
     * @param start 下一个要拼接的字符的起始下标
     */
    const backtrack = (path, l, start) =>{
        //子集长度满足条件时返回
        if (path.length === l){
            res.push(path);
            return;
        }
        for (let i = start; i<nums.length; i++){
            backtrack(path.concat(nums[i]),l,i+1);
        }
    };
    //数组子集的长度可能为0到n
    for (let i = 0; i <= nums.length; i++) {
        backtrack([],i,0);
    }
    return res;
}

//时间复杂度：O(2^n)
//空间复杂度：O(n)